﻿//最长递增子序列(medium): https://leetcode.cn/problems/longest-increasing-subsequence/description/
class Solution {
public:
    int memo[2510];
    int ret=0;
    int n;
    int lengthOfLIS(vector<int>& nums) {
        n=nums.size();
        for(int i=0;i<n;i++)
        {
            ret=max(dfs(i,nums),ret);
        }
        return ret;
    }
    int dfs(int pos,vector<int>& nums)   //放回pos位置为起点的最长递增子序列
    {
        if(pos>=n)  
        {
            return 0;
        }
        if(memo[pos])
        {
            return memo[pos];
        }
        int Max=1;
        for(int i=pos+1;i<n;i++)
        {
            if(nums[i]>nums[pos])
            {
                Max=max(dfs(i,nums)+1,Max);
            }
        }
        memo[pos]=Max;
        return Max;
    }
};

//猜数字大小| | (medium): https://leetcode.cn/problems/guess-number-higher-or-lower-ii/
class Solution {
public:
    int memo[210][210];
    int getMoneyAmount(int n) {
        return dfs(1,n);
    }
    int dfs(int left,int right)   //区间的最大成本
    {
        if(left>=right)   return 0;    //相当于找到了
        if(memo[left][right])   return memo[left][right];
        int ret=INT_MAX;
        for(int head=left;head<=right;head++)
        {
            int x=dfs(left,head-1);
            int y=dfs(head+1,right);
            memo[left][head-1]=x;
            memo[head+1][right]=y;
            ret=min(ret,max(x,y)+head);
        }
        memo[left][right]=ret;
        return ret;
    }
};